Wireless local area networks (WLANs), such as a wireless medium in a communication network using Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), are founded on the principles of collision avoidance. Such networks may also conform to a communication standard such as a communication protocol of 802.11 type e.g. Medium Access Control (MAC). The collision avoidance approach aims to separate concurrent transmissions in space and time. Packets of e.g. data are corrupted due to collision or channel fading. The transmitter remains unaware of the corruption and continues to transmit the entire packet unnecessarily. Eventually, based on the absence of an acknowledgment from the receiver, the transmitter infers packet loss, and prepares for retransmission.
The IEEE 802.11 standard defines the way WLANs must work at the physical and medium access control (MAC) level. Typically, the 802.11 MAC (Medium Access Control) relies on a contention-based mechanism based on a technique called “Carrier Sense Multiple Access with Collision Avoidance” (CSMA/CA). The standard 802.11 medium access protocol is essentially to wait for the medium to become idle.
Carrier sensing is performed by both physical and virtual mechanisms. The virtual carrier sensing is achieved by transmitting control packets to reserve the medium prior to transmission of data packets. The transmitter attempts to sense an idle medium for at least a DIFS (distributed interframe spacing) duration of time. If the medium is sensed busy, the transmitter waits until it becomes idle and then starts a countdown back-off timer set to expire after a number of slot times, chosen randomly between [0,CW] (i.e. the contention window, CW being an integer value).
More precisely, the period of back-off timer countdown is called the ‘back-off procedure’, and is implemented as follows:
Upon starting the back-off process, prior to data transmission, a station initializes its back-off time counter to a ‘random value’. The back-off time counter is decremented once every time interval for so long as the channel is sensed to be idle (e.g. with reference to FIG. 3, count down starting from T0), halted (or frozen) when a transmission is detected on the channel (e.g. with reference to FIG. 3, count down stopping at T1), and reactivated when the channel is sensed idle again (e.g. with reference to FIG. 3, T2). When its back-off time counter reaches zero, a station transmits a DATA message (or ready-to-send (RTS) message as explained hereafter) which contains the address of the receiver and the duration for which the medium is to be reserved for that message. A collision occurs when two or more stations start transmission simultaneously (e.g. when their own back-off counter has reached zero around the same time). Ideally, the same number of slots is present among all nodes forming the 802.11 cell during the back-off countdown procedure. This may not be always the case in reality, because of inaccuracies in 802.11 quartz which results in clock drifts. The quartz is comprised in the node to be used as a timer device facilitating the countdown process. Different quartz crystals have slightly varying characteristics. A communication standard can specify the accuracy of the quartz which is required for compliance but differences remain. Such differences lead to clock drift.
Since the CSMA/CA protocol does not rely on the capability of the stations to detect a collision by hearing their own transmission, a positive acknowledgement (ACK) is transmitted by the destination station to signal the successful packet reception. The ACK is immediately transmitted at the end of the packet, after a period of time called Short InterFrame Space (SIFS). If the transmitting station does not receive the ACK within a specified ACK Timeout, or it detects the transmission of a different packet on the channel, it reschedules the packet transmission according to the given back-off rules.
Collision Avoidance is more specifically enhanced by a four-way handshaking mechanism called RTS/CTS (request-to-send/clear-to-send) exchange, which is a recommended option of the 802.11 standard.
According to 802.11 standard, to protect transmissions from collisions, a station may begin a transmission sequence with an RTS/CTS exchange. A node will issue a Medium access request (RTS) to a destination node, when the sender node requires data transmission on the 802.11 medium. The duration specified in the RTS is the duration of the entire exchange including the control packets (i.e. including RTS/CTS message exchange). When the intended receiver receives the RTS, and senses the medium to be free, this destination node replies with a Clear-to-send (CTS) message, after waiting for one SIFS (Short InterFrame spacing) period, thereby acknowledging the request and indicating readiness to receive data. The CTS also contains the duration of the entire exchange from that point of time. The transmitter, upon receiving the CTS, transmits the DATA packet after an SIFS period. The receiver responds back with an ACK after an SIFS period following its complete receipt of the DATA packet.
Each wireless node maintains a data structure called the network allocation vector (NAV) to store the aggregate duration of time it knows that the medium would be busy. Any node that hears a packet that is not for itself, sets its NAV for the time duration mentioned in the packet header, which is equal to the time required to transmit all control and data packets. This prevents these nodes from transmitting any packets during the period the NAV is set. It is possible that the receiver does not receive the RTS correctly because of a collision or fading. Even if it does, it may not always respond with a CTS because, for example, the NAV is set. In any case, the transmitter goes through the random back-off and retries. The RTS/CTS mechanism is very effective in terms of system performance, especially when large packets are considered, as it reduces the length of the frames involved in the contention process. In fact, in the assumption of perfect channel sensing by every station, collision may occur only when two (or more) packets are transmitted within the same slot time. If both transmitting stations employ the RTS/CTS mechanism, collision occurs only on the RTS frames, and it is detected quickly by the transmitting stations due to the lack of CTS responses.
In reality, 802.11 nodes suffer from quartz drifting, resulting in clock and timers jittering (typically a value of 100 ppm accuracy is recommended for 802.11 devices). Compared to back-off slot granularity (9 μs in 802.11n), drifting time is not negligible: there is no certainty of access to a given targeted back-off slot.
US patent application 2009/0052429 A1 discloses a method for synchronizing communications in a wireless mesh network. Each of a plurality of network devices are synchronized to an absolute timing based on an absolute slot number.
US patent application 2009/0141738 A1 discloses a time slot system where a back-off counter value determination engine selects an unreserved time slot for a next transmission and a medium access engine for initiating a current transmission. This patent uses a reservation-based distributed collision avoidance channel access in a wireless area network. By advertising the future channel access parameters in advance, nodes reduce the number of collisions. Any extra functionality devised to maintain the reservation procedure adds overhead to the functioning of the device and consumes more bandwidth, both situations being very undesirable.
The IEEE 802.11 Standard provides some clock synchronization services. First, it provides a Time Synchronization Function (TSF), through which all stations synchronize their local MAC-layer protocol timers to the “timestamps” (actually 64-bit microsecond counter values) broadcast in periodic beacon frames sent randomly by 802.11 stations in a distributed ad-hoc environment (there is no access point in such a configuration). Separate from the TSF, the IEEE 802.11 standard also includes an optional capability called MLME-HL-SYNC in the MAC-layer management entity (MLME), which is intended to support application-layer time synchronization protocols.
Unfortunately, neither the TSF timer nor the MLME-HL-SYNC capability can match high specification precision timing requirements of a medium access where drift should be less than half a back-off slot. In particular, the specified tolerances for the TSF timer are relatively relaxed (±0.01%). In practice, its accuracy is likely to be substantially worse because the update mechanism does not account for variability in MAC-layer channel access delays. Moreover, the role of the MLME is strictly limited to issuing the MLME-HL-SYNC.indication primitive at certain end-of-packet events; the MAC client assumes full responsibility for generating the timestamp to this event by consulting an external clock.
Thus the problem of clock drift is limiting to the optimal functioning of wireless medium access.